package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月23日
*时间：下午7:15:39
*/
public class Q79 {
    public int longestCommonSubstring(String a, String b) {
        if (a == null || b == null || a.length() == 0 || b.length() == 0) {
            return 0;
        }
        int[][] lenth = new int[a.length()][b.length()];
        int max = 0;
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    if (i == 0 || j == 0) {
                        lenth[i][j] = 1;
                        if (lenth[i][j] > max) {
                            max = lenth[i][j];
                        }
                    } else {
                        lenth[i][j] = lenth[i - 1][j - 1] + 1;
                        if (lenth[i][j] > max) {
                            max = lenth[i][j];
                        }
                    }
                }
            }
        }
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                System.out.print(lenth[i][j] + "\t");
            }
            System.out.println();
        }
        return max;
    }

    @Test
    public void TestA() {
        System.out.println(longestCommonSubstring("ABCD", "CBCDE"));
    }
}
